/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package collections.maps;

import java.util.HashMap;
import java.util.Iterator;
import sun.java2d.pipe.SpanShapeRenderer;
import sun.security.krb5.internal.EncAPRepPart;

/**
 *
 * @author harker777
 */
public class MyHashMap implements MyMap {

	private class SimpleEntry implements MyMap.Entry {

		private Object key;
		private Object value;
		private SimpleEntry next;

		public SimpleEntry getNext() {
			return next;
		}

		public boolean hasNext() {
			return next != null;
		}

		public void setNext(SimpleEntry next) {
			this.next = next;
		}

		public SimpleEntry(Object key, Object value) {
			this.key = key;
			this.value = value;
		}

		@Override
		public Object getKey() {
			return key;
		}

		@Override
		public Object getValue() {
			return value;
		}

		@Override
		public int hashcode() {
			return key.hashCode();
		}

		@Override
		public Object setValue(Object value) {
			Object oldValue = this.value;
			this.value = value;
			return oldValue;
		}

		@Override
		public String toString() {
			return "<" + key + " : " + value + ">";
		}
	}
	private static final int DEFAULT_CAPACITY = 16;
	private static final float DEFAULT_LOAD_FACTOR = 0.75F;
	private int size;
	public int capacity;
	private float loadFactor;
	private SimpleEntry[] buckets;

	public MyHashMap(int initialCapacity, float loadFactor) {
		capacity = findClosestGoodCapacity(initialCapacity);
		this.loadFactor = loadFactor;
		buckets = new SimpleEntry[capacity];
		size = 0;
	}

	public MyHashMap(int initialCapacity) {
		this(initialCapacity, DEFAULT_LOAD_FACTOR);
	}

	public MyHashMap() {
		this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
	}

	// Capacity should be power of two for easy search
	private int findClosestGoodCapacity(int capacity) {
		int result = 1;
		while (result < capacity) {
			result <<= 1;
		}
		return result;
	}

	@Override
	public void clear() {
		for (int i = 0; i < capacity; i++) {
			buckets[i] = null;
		}
		size = 0;
	}

	private int findHashCode(Object key) {
		return (key == null) ? 0 : key.hashCode();
	}

	@Override
	public boolean containsKey(Object key) {
		int hashCode = findHashCode(key);
		int bucketNum = findBucketForHash(hashCode);
		SimpleEntry bucket = buckets[bucketNum];

		SimpleEntry targetBucket = findInBucket(key, bucket);
		return !(targetBucket == null);
	}

	@Override
	public Object get(Object key) {
		int hashCode = findHashCode(key);
		int bucketNum = findBucketForHash(hashCode);
		SimpleEntry bucket = buckets[bucketNum];

		SimpleEntry targetBucket = findInBucket(key, bucket);
		return (targetBucket == null) ? null : targetBucket.getValue();
	}

	private SimpleEntry findInBucket(Object key, SimpleEntry bucket) {
		if (bucket == null) {
			return null;
		}
		if (isKeyInBucketEntry(key, bucket)) {
			return bucket;
		}

		while (bucket.hasNext()) {
			bucket = bucket.getNext();
			if (isKeyInBucketEntry(key, bucket)) {
				return bucket;
			}
		}

		return null;
	}

	private boolean isKeyInBucketEntry(Object key, SimpleEntry entry) {
		if (key == null) {
			if (entry.getKey() == null) {
				return true;
			} else {
				return false;
			}
		}

		if (key.equals(entry.getKey())) {
			return true;
		} else {
			return false;
		}
	}

	private int finBucketForHash(int hashCode, int someCapacity) {
		return (hashCode & (someCapacity - 1));
	}

	private int findBucketForHash(int hashCode) {
		return finBucketForHash(hashCode, capacity);
	}

	@Override
	public boolean isEmpty() {
		return size <= 0;
	}

	private SimpleEntry getLastEntry(SimpleEntry bucket) {
		SimpleEntry localBucket = bucket;
		while (localBucket.hasNext()) {
			localBucket = localBucket.getNext();
		}
		return localBucket;
	}

	@Override
	public Object put(Object key, Object value) {
		int hashCode = findHashCode(key);
		int bucketNum = findBucketForHash(hashCode);
		SimpleEntry bucket = buckets[bucketNum];

		if (bucket == null) {
			putFirstInBucket(key, value, bucketNum);
			resizeIfNeeded();
			return null;
		}

		SimpleEntry oldEntry = findInBucket(key, bucket);
		Object oldValue = (oldEntry == null) ? null : oldEntry.getValue();

		if (oldEntry != null) {
			oldEntry.setValue(value);
		} else {
			addItemToBucket(bucket, key, value);
			resizeIfNeeded();
		}

		return oldValue;
	}

	private void addItemToBucket(SimpleEntry bucket, Object key, Object value) {
		SimpleEntry place = getLastEntry(bucket);
		SimpleEntry newEntry = new SimpleEntry(key, value);
		place.setNext(newEntry);
		size++;
	}

	private void putFirstInBucket(Object key, Object value, int bucketNum) {
		buckets[bucketNum] = new SimpleEntry(key, value);
		size++;
	}

	private boolean resizeIfNeeded() {
		int neededSize = size + 1;
		int threshold = (int) Math.ceil(capacity * loadFactor);

		if (neededSize > threshold) {
			resize();
			return true;
		}
		return false;
	}

	private void resize() {
		int newCapacity = capacity << 1;
		SimpleEntry[] oldBuckets = buckets;
		buckets = new SimpleEntry[newCapacity];
		capacity = newCapacity;
		size = 0;

		for (int i = 0; i < oldBuckets.length; i++) {
			SimpleEntry bucket = oldBuckets[i];
			if (bucket != null) {
				do {
					Object key = bucket.getKey();
					Object value = bucket.getValue();
					put(key, value);
					bucket = bucket.getNext();
				} while (bucket != null);
			}
		}
	}

	@Override
	public Object remove(Object key) {
		int hashCode = findHashCode(key);
		int bucketNum = findBucketForHash(hashCode);
		SimpleEntry bucket = buckets[bucketNum];
		if (bucket == null) {
			return null;
		}

		if ((bucket.getNext() == null)) {
			if (bucket.getKey().equals(key)) {
				size--;
				Object oldObject = bucket.getValue();
				buckets[bucketNum] = null;
				return oldObject;
			}
			return null;
		}

		if (bucket.getKey().equals(key)) {
			size--;
			Object oldObject = bucket.getValue();
			buckets[bucketNum] = bucket.getNext();
			return oldObject;
		}
		
		SimpleEntry previous = bucket;
		SimpleEntry current = bucket.getNext();

		while ((current != null) && (!current.getKey().equals(key))) {
			previous = previous.getNext();
			current = current.getNext();
		}

		if (current == null) {
			return null;
		} else{
			size--;
			Object oldObject = current.getValue();
			previous.setNext(current.getNext());
			return oldObject;
		}
	}

	@Override
	public int size() {
		return size;
	}

	private class EntryIterator implements Iterator{

		int currentBucket;
		SimpleEntry currentEntry;
		
		public EntryIterator(){
			currentBucket = -1;
			currentEntry = null;
		}
	
		@Override
		public boolean hasNext() {
			if ((currentBucket == capacity - 1) && (currentEntry == null)){
				return false;
			}
			if (isEmpty()){
				return false;
			}
			return true;
		}

		@Override
		public Object next() {
			if (currentBucket >= capacity){
				return null;
			}
			
			if (currentEntry == null) {
				currentBucket++;
				currentEntry = buckets[currentBucket];
				if (currentEntry != null){
					return currentEntry;
				}
				return next();
			} else{
				Object value = currentEntry;
				currentEntry = currentEntry.getNext();
				return value;
			}
		}

		@Override
		public void remove() {
			MyHashMap.this.remove(currentEntry.getKey());
		}
	}
	
	@Override
	public Iterator entryIterator() {
		return new EntryIterator();
	}

	@Override
	public String toString() {
		String result = "{\n";
		for (int i = 0; i < capacity; i++) {
			result += "[";
			SimpleEntry bucket = buckets[i];
			if (bucket != null) {
				do {
					result += bucket.toString() + ";";
					bucket = bucket.getNext();
				} while (bucket != null);
			}

			result += "]\n";
		}
		result += "}";
		return result;
	}
}
